package sort;

/**
 * @Author: Ma JiBin
 * @Email: 1423553596@qq.com
 * @Date: 2018/10/28 14:33
 * @Description: 并归排序算法
 * 算法思想：将数组划分为许多小数组，对小数组进行排序，再对小数组进行一一有序合并，最终合并成一个有序数组
 */
public class MergeSort {

    /**
     * 合并两个有序的数组方法
     * @param arr 目标数组
     * @param start1
     * @param end1
     * @param start2
     * @param end2
     */
    public void sort(int[] arr,int start1,int end1,int start2,int end2){
        //临时数组
        int[] a = new int [end2 - start1 + 1];
        int i = 0;
        int start = start1;
        //比较两个数组中的元素，将小的先插入a数组中
        while(start1 <= end1 && start2 <= end2){
            if(arr[start1] <= arr[start2]){
                a[i] = arr[start1];
                start1 ++;
                i ++;
                continue;
            }
            if(arr[start1] > arr[start2]){
                a[i] = arr[start2];
                start2 ++;
                i ++;
                continue;
            }

        }

        //将剩余的插入到a数组中
        while(start1 <= end1){
            a[i] = arr[start1];
            i ++;
            start1 ++;
        }

        //将剩余的插入到a数组中
        while(start2 <= end2){
            a[i] = arr[start2];
            i ++;
            start2 ++;
        }

        //将临时数组a复制到原数组中
        for(int j = 0;j < a.length;j ++){
            arr[start + j] = a[j];
        }
    }

    /**
     * 将数组拆分为小数组，排序后再调用sort方法进行合并
     * @param s
     * @param start
     * @param end
     */
    public void mergeSort(int[] s, int start, int end) {
        if (start >= end) {
            return;
        }

        //将数组分为两段，记下下标直到每段只有一个数为止
        int m = (start + end) / 2;
        int start1 = start;
        int end1 = m;
        int start2 = m + 1;
        int end2 = end;
        //递归调用此方法
        this.mergeSort(s, start1, end1);
        this.mergeSort(s, start2, end2);

        //当start == end时,递归调用mergeSort方法退出，调用此方法，对两个有序数组进行合并
        //this.merge(s, start1, end1, start2, end2);
        this.sort(s, start1, end1, start2, end2);
    }

    /**
     * 合并两个有序数组为一个有序数组
     * @param s
     * @param start1
     * @param end1
     * @param start2
     * @param end2
     */
    private void merge(int[] s, int start1, int end1, int start2, int end2) {
        System.out.printf("\n开始合并,合并范围,[%d,%d],[%d,%d]", start1, end1, start2, end2);
        int start = start1;
        // 临时数组
        int[] t = new int[end2 - start1 + 1];
        // 临时数组下标
        int i = 0;

        // 比较开始
        while (start1 <= end1 && start2 <= end2) {
            if (s[start1] < s[start2]) {
                t[i] = s[start1];
                start1++;
                i++;
                continue;
            }
            if (s[start1] > s[start2]) {
                t[i] = s[start2];
                start2++;
                i++;
                continue;
            }
        }

        // 拷贝剩余元素
        while (start1 <= end1) {
            t[i] = s[start1];
            start1++;
            i++;
        }

        // 拷贝剩余元素
        while (start2 <= end2) {
            t[i] = s[start2];
            start2++;
            i++;
        }

        // 将已排好序的元素放回对应位置
        for (i = 0; i < t.length; i++) {
            s[start + i] = t[i];
        }

        // 打印数组
        PrintArray(s);
    }

    /**
     * 打印数组方法
     * @param s
     */
    private static void PrintArray(int[] s) {
        System.out.print("\n下标:");
        for (int p = 0; p < s.length; p++) {
            System.out.printf("%2d,", p);
        }
        System.out.print("\n值值:");
        for (Integer m : s) {
            System.out.printf("%2d,", m);
        }
        System.out.print("\n-----------------------------");
    }

    public static void main(String[] args) {
        int[] s = new int[] { 9, 2, 3, 7, 6, 5, 8, 4,2,99,324};

        // 打印数组
        PrintArray(s);

        MergeSort mergeSort = new MergeSort();
        mergeSort.mergeSort(s, 0, s.length - 1);

        // 打印数组
        PrintArray(s);
    }
}
